1. Field of the Invention
The present invention relates to a system and method for using weights associated with various network operators to determine the optimal link for use in Layer II routing in a network, such as an 802.11 network. More particularly, the present invention relates to a system and method for using weights assigned to links associated with particular network systems in an overlapping multiple system environment to compute the optimum path between nodes in a communication network, such as an 802.11 network, in order to select the most suitable link over which to send data packets between the nodes.
2. Description of the Related Art
In recent years, a type of mobile communications network known as an “ad-hoc” network has been developed. In this type of network, each user terminal (hereinafter “mobile node”) is capable of operating as a base station or router for the other mobile nodes, thus eliminating the need for a fixed infrastructure of base stations. Accordingly, data packets being sent from a source mobile node to a destination mobile node are typically routed through a number of intermediate mobile nodes before reaching the destination mobile node.
Details of an ad-hoc network are set forth in U.S. Pat. No. 5,943,322 to Mayor, the entire content of which is incorporated herein by reference. More sophisticated ad-hoc networks are also being developed which, in addition to enabling mobile nodes to communicate with each other as in a conventional ad-hoc network, further enable the mobile nodes to access a fixed network and thus communicate with other types of user terminals, such as those on the public switched telephone network (PSTN) and on other networks such as the Internet. Details of these types of ad-hoc networks are described in U.S. patent application Ser. No. 09/897,790 entitled “Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks”, filed on Jun. 29, 2001, in U.S. patent application Ser. No. 09/815,157 entitled “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel”, filed on Mar. 22, 2001, and in U.S. patent application Ser. No. 09/815,164 entitled “Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System”, filed on Mar. 22, 2001, the entire content of each of said patent applications being incorporated herein by reference.
As can be appreciated by one skilled in the art, when a node sends packetized data to a destination node, the node typically checks its routing table to determine whether the destination node is contained in its routing table. If the destination node is contained in the node's routing table, the data is transmitted via a path that leads to the destination node. If the destination node is not listed in the node's routing table, then the packet is sent to one or more other nodes listed in the node's routing table, and those other nodes determine if the destination table is listed in their routing tables. The process continues until the data packet eventually reaches the destination node.
In these types of ad-hoc networks, the algorithms that are used to determine the path of intermediate nodes via which the data packets are routed between source and destination nodes are typically based on the shortest distance between the source and destination nodes or, assuming that the data packet transport medium is wireless, the least power required to perform the routing. However, such algorithms do not necessarily optimize the cost associated with delivery of data packets. For example, routing of data packets can be delayed due to congestion in intermediate nodes. Also, delivery failure of data packets can occur on noisy radio links between nodes. Moreover, because many of the nodes are mobile, the conditions of the links can be constantly changing. Finally, some routes may require the use of equipment belonging to another network, and therefore incur an additional cost for delivery.
Currently, ad-hoc wireless communications networks, and especially those employing terminals which operate in accordance with 802.11 standards, do not take into account the cost associated with the use of “out of network” equipment when determining the suitability of a link for use in sending data packets between nodes. Details of the 802.11 standards are set forth in ISO/IEC 8802-11, ANSI/IEEE 802.11 “Information Technology—Telecommunications and Information Exchange Between Systems—Local and Metropolitan Area Network Specific Requirements”, Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications, the entire contents of which being incorporated herein by reference. Also, a description of the 802.11 standard is found in a book by Bob O'Hara and Al Petrick entitled IEEE 802.11 Handbook: A Designer's Companion, IEEE, 1999, the entire contents of which being incorporated herein by reference.
In cellular systems, it is common for operators of different cellular systems to form cooperative agreements with one another so that subscribers of either system can utilize the infrastructure of either system. The cellular system operators typically form inter-system service level agreements which define how each system will account for and be compensated for usage of the system by subscribers of another system. In this manner, cellular system operators can offer subscribers access to more infrastructure and therefore a broader coverage area.
Similarly, it is possible for the service areas of multiple ad-hoc peer-to-peer networks to overlap. When they do, it is often advantageous for the operators of the multiple networks to enter into inter-system service level agreements to allow cooperative routing between network elements in the multiple systems. Unfortunately, there is an opportunity for fraud and abuse in this system when a system operator falsely advertises routes to gain more traffic share, or to starve another system of traffic load. Even in the absence of fraud or abuse, it would be advantageous for a system operator to selectively choose routes according to the system associated with the infrastructure utilized in each route.
Accordingly, a need exists for a system and method which enables a wireless ad-hoc communications network, such as an 802.11 network, to evaluate the cost associated with various links between nodes in order to determine which link to use for data packet routing between the nodes. The cost is based at least in part on the system to which equipment along the link belongs, and the inter-system service level agreements in place between system operators.